package medium;

import java.util.ArrayList;
import java.util.List;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/6/10 19:29
 */
public class No5_最长回文子串 {
    public static void main(String[] args) {
        Solution5 solution5 = new Solution5();
        String res = solution5.longestPalindrome("babcbabcbax");
        System.out.println(res);
    }
}

class Solution5 {
    public String longestPalindrome(String s) {
        //马拉车算法,理解难度系数0.2,跟KMP有的一拼!!!
        //时间复杂度O(n),思路大致如下:
        //不需要特意掌握,重在参与
        //1.定义中心轴center,右边界mx
        int center = -1;
        int mx = -1;

        //最大回文长度
        int big = 0;
        String res = "";
        //对称数组
        List<Integer> list = new ArrayList<>();
        
        //处理s
        StringBuffer ss = new StringBuffer();
        ss.append("#");
        for (char c : s.toCharArray()) {
            ss.append(c).append("#");
        }
        s = ss.toString();
        
        //2.遍历每个字符位置
        for (int i = 0; i < s.length(); i++) {
            //每一个字符都有回文半径
            int len = 0;
            //3.假如中心轴回文半径在[x,mx] (指的索引从x到mx(含))
            if (i < mx) {
                //① 如果字符位置i<mx,则获取其对称位置
                int duicheng = 2 * center - i;
                //one.如果对称位置其右边界超过中心轴
                //mx-i
                //two.如果对称位置其右边界没有超过中心轴
                //对称位置的值(回文半径)
                //考虑周全
                int minLen = Math.min(mx - i, list.get(duicheng));
                //最终的len
                len = getHR(s, i - minLen, i + minLen);
            } else {
                //② 如果字符位置>=mx,只能硬算
                len = getHR(s, i, i);
            } 
            
            //len处理完加List
            list.add(len);
            //4.如果当前字符最右边界在范围外,则最右边界变为当前最右边界
            if (i + len > mx) {
                mx = i + len;
                //注意中心联动
                center = i;
            }
            
            //获取回文串
            if (len > big) {
                big = len;
                res = s.substring(i - big, i + big + 1);
            }
        }
        
        
        //5.最后获取最长回文串
        return res.replaceAll("#", "");
    }

    public int getHR(String data, int left, int right) {
        while (left >= 0 && right < data.length() && data.charAt(left) == data.charAt(right)) {
            left--;
            right++;
        }
        return (right - left - 2) / 2;
    }
}



    //public String longestPalindrome(String s) {
    //    //中心扩展->莫挨老子
    //    int l = s.length();
    //    int max = 0;
    //    String res = "";
    //    //每个老子逐个遍历
    //    for (int blue = 0; blue < l; blue++) {
    //        //每个老子都要进行左右扩散
    //        int red = blue - 1; //左
    //        int green = blue + 1;//右
    //        //先判断挨着的
    //        while (red >= 0 && s.charAt(red) == s.charAt(blue)) {
    //            red--;
    //        }
    //        while (green < l && s.charAt(green) == s.charAt(blue)) {
    //            //也得远离
    //            green++;
    //        }
    //        //green跟red全部远离,这时候有可能相同
    //        while (red >= 0 && green < l && s.charAt(red) == s.charAt(green)) {
    //            //你跟我相同,莫挨
    //            red--;
    //            green++;
    //        }
    //        
    //        //经过以上判断,red跟green位置指向的值一定不同
    //        //同时,它们包含的子串一定是回文串
    //        
    //        //现在获取最大回文串!
    //        if (max < green - red - 1) {
    //            //回文串长度
    //            max = green - red - 1;
    //            res = s.substring(red + 1, green);
    //        }
    //    }
    //    return res;
    //}



    //public String longestPalindrome(String s) {
    //    //动态规划
    //    //定义dp[x][y]为索引x,y(含)围成的子串的回文串?true,false
    //    //获取最大长度
    //    int l = s.length();
    //    boolean[][] dp = new boolean[l][l];
    //    int max = 0;
    //    String res = "";
    //    for (int i = 0; i < l; i++) {
    //        dp[i][i] = true;
    //        int x = 0;
    //        for (int j = i; j < l; j++) {
    //            int y = j;
    //            //处理逻辑
    //            //搞出动态规划方程式子
    //            //处理边界条件
    //            if (x == y) {
    //                dp[x][y] = true;
    //            } else if (y - x == 1) {
    //                //长度为2
    //                if (s.charAt(y) == s.charAt(x)) {
    //                    dp[x][y] = true;
    //                }
    //            } else if (y - x > 1) {
    //                //if() 写越界不需要
    //                dp[x][y] = (dp[x + 1][y - 1]) && (s.charAt(x) == s.charAt(y));
    //            }
    //            
    //            //每次循环完一个长度,记录最长回文串
    //            if (dp[x][y]) {
    //                if (max < y - x + 1) {
    //                    max = y - x + 1;
    //                    res = s.substring(x, y + 1);
    //                }
    //            }
    //            
    //            x++;
    //        }
    //        
    //    }
    //    return res;
    //}



    //public String longestPalindrome(String s) {
    //    //暴力法:双指针暴力
    //    int l = s.lengh();
    //    //定义影子
    //    int start = 0;
    //    int end = -759;
    //    int max = 0;
    //    //需求
    //    String res = "";
    //    //固定绿指针
    //    for (int green = l - 1; green >= 0; green--) {
    //        //倒序遍历
    //        //获取基准字母
    //        char base = s.charAt(green);
    //        for (int red = 0; red <= green; red++) {
    //            //获取red与base相同的所有位置
    //            if (s.charAt(red) == base) {
    //                //影子产生
    //                //是为了判断回文
    //                start = red;
    //                end = green;
    //                while (start <= end) {
    //                    if (s.charAt(start) == s.charAt(end)) {
    //                        //影子移动
    //                        start++;
    //                        end--;
    //                    } else {
    //                        break;
    //                    } 
    //                }
    //                if (start > end) {
    //                    //说明是回文
    //                    //获取回文长度
    //                    //max = 0??
    //                    if (green - red + 1 > max) {
    //                        max = green - red + 1;
    //                        res = s.substring(red, green + 1);
    //                    }
    //                        
    //                }
    //            }
    //        }
    //    }
    //    return res;
    //}

    //public String longestPalindrome(String s) {
    //    //暴力法
    //    //获取s长度
    //    int l = s.length();
    //    //需求回文串
    //    String res = "";
    //    for (int i = 0; i < l; i++) {
    //        for (int j = 0; i + j < l; j++) {
    //            //为啥要用? 因为里面有个反转方法,懒得写啦
    //            StringBuffer check = new StringBuffer();
    //            
    //            //要判断的字符串
    //            //add:"cac"
    //            String add = s.substring(j, i + j + 1);
    //            //判断回文
    //            check.append(add);
    //            if (add.equals(check.reverse().toString())) {
    //                //就是回文
    //                res = add;
    //                break;
    //            }
    //            
    //        }
    //    }
    //    return res;
    //}






